class Solution {
private:
    TreeNode* merge_trees(TreeNode* lt, TreeNode* rt) {
        if (lt == nullptr) return rt;
        if (rt == nullptr) return lt;
        if (lt->val < rt->val) {
            rt->left = merge_trees(lt, rt->left);
            return rt;
        } else {
            lt->right = merge_trees(lt->right, rt);
            return lt;
        }
    }
    TreeNode* partition(vector<int>& nums, int s, int e) {
        if (s >= e) return nullptr;
        if (s + 1 == e) return new TreeNode(nums[s]);
        int m = s + (e - s) / 2;
        TreeNode* lt = partition(nums, s, m), * rt = partition(nums, m, e);
        return merge_trees(lt, rt);
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return partition(nums, 0, (int)nums.size());
    }
};
